1. Technical Field of the Invention
The present invention relates to a three-dimensional shape data recording/displaying method and device, and to a three-dimensional shape measuring method and device, for measuring a non-moving three-dimensional shape from a plurality of measuring positions, and for combining and restoring the distance data thereof.
2. Description of the Related Art
Three-dimensional shape measuring technologies are becoming more prevalent, and three-dimensional shape data is used in a variety of application fields, such as measuring shapes in machine components/workpieces, automatic position identification in mobile robots, and topographical and structural measurements, and the like.
Conventionally, point sets, range imagery, surfaces, voxel structures, and the like, have been used as three-dimensional shape data recording/displaying methods and devices.
Point sets express shapes by coordinate values of measured points, which are sensor measured data. Additionally, range imagery expresses shapes by maintaining range values, in the depth direction, for each picture element of a two-dimensional image. Surfaces express the surface shapes of objects through assembling together triangular shapes. Voxel structures are structures in which a space is divided into small rectangular solids, and shape information is held within each voxel.
The measured data in three-dimensional shape measuring is expressed in polar coordinate values (r, θ, φ, with the measuring position being the origin, for example. In the present invention, this data is known as “range data.”
There are the following problems when non-moving three-dimensional shapes are reproduced through integrating range data from a plurality of positions.
When point sets are used, the amount of data increases proportionately with the measured data. Consequently, the total data size is excessive when the object being measured is large. Because of this, this is not practical as a data structure for expressing shapes.
When range imagery is used, the measurement is from one direction, and the greater the distance, the wider the spacing of the picture elements, and the less the resolution. Moreover, because this can express data from only one direction, this technology is not directed at integrating measurement results from a plurality of observation points.
When surfaces are used, high-speed processing is difficult due to the need for complex processing in the integration thereof.
In contrast, the voxel structure has the benefits of having a constant data size, being able to integrate data from a plurality of observation points, and not requiring complex calculations to integrate the data, and is the most suited to reproduction through integrating range data from a plurality of positions.
Moreover, Japanese Patent 3170345 and Japanese Unexamined Patent Application Publication JP09-81788A, and non-patent document “Learning Occupancy GridMaps with Forward Sensor Models” by Sebastian Thrun, have disclosed improved voxel structures.
In Japanese Patent 3170345, a method known as “voxel voting” is used to poll the measurement results at each voxel, to integrate three-dimensional shapes from a plurality of observation points. Furthermore, this method discloses a method for controlling data hierarchically through further oct tree partitioning of voxels for voxels unable to obtain adequate resolution.
Japanese Unexamined Patent Application Publication JP09-81788A proposes means for accumulating probability values for each voxel. With these means, the environment model is integrated independent of frequency through the application of probabilities, enabling the creation of accurate environment models.
Non-patent document “Learning Occupancy Grid Maps with Forward Sensor Models” by Sebastian Thrun, while envisioning planar surfaces, proposes a method for restoring, to correct values, incorrect voxel probability values that have occurred due to errors in the measured data of voxels that hold probability values.
Additionally, non-patent document “Development of a Three-Dimensional Laser Radar,” by Sekimoto Kiyohide, et al., Ishikawajima-Harima Engineering Review, vol. 43, No. 4 (2003-7), disclosed a technology relating to the present invention.
The voxel structure of Japanese Patent 3170345 repetitively divides voxels in order to obtain the correct shapes, but there is a problem in that the data size increases when the number of partitions is increased. Because of this, typically the depth of partitioning is fixed, so there is a limit on the resolution. That is, resolutions in excess of the size of the voxels after partitioning cannot be expressed. Additionally, voxels wherein errors have occurred due to data that contains errors exist as is. Because of this, data that contains errors cannot be handled.
The voxel structure of Japanese Unexamined Patent Application Publication JP09-81788A expresses shape using probability values, but when the data contains error, as with Japanese Patent 3170345, the voxel wherein the error has occurred remains as is. Because of this, data that contains errors cannot be handled.
The voxel structure of non-patent document “Learning Occupancy Grid Maps with Forward Sensor Models” by Sebastian Thrun includes a probability decreasing process, and thus has a function for eliminating voxels that have incorrect probability values. However, typically voxels contain both regions wherein measurement objects exist and regions wherein measurement objects do not exist, so there is a problem of non-convergence to the correct shape even when a plurality of measurements is integrated.